package leetcode.hot100;

import java.util.ArrayList;

/**
 * 任务调度器
 */

public class Solution621 {

    public static void main(String[] args) {
        char[] tasks = new char[]{'A','A','A','B','B','B'};
        int n = 2;
        System.out.println(new Solution621().leastInterval(tasks,n));
    }

    public int leastInterval(char[] tasks, int n) {
        //贪心，每次都找一个与前面n个任务不同的任务，实在找不到就待命

        //1，统计各类任务数，映射后不用再考虑字符，只考虑下标作为任务类型即可
        int[] taskCount = new int[26];
        for (int i = 0; i < tasks.length; i++) {
            taskCount[tasks[i]-'A']++;
        }

        //2，调度
        int[] freezeTime = new int[26]; //剩余冷却时间
        int totalTime = 0; //花费总时间
        int i = 0; //已调度的任务数
        while (i<tasks.length){
            //从冷却时间为0的任务中调度，并且调度剩余任务最多的那个
            //记录选取的任务和它对应的剩余次数,另外记录被冷却的最小时间，方便时间计算
            int select = -1, leftNum = 0, minFreeze = n+1;
            for (int j = 0; j < 26; j++) {
                if(freezeTime[j]>0&&taskCount[j]>0) minFreeze = Math.min(minFreeze,freezeTime[j]);
                if(freezeTime[j]==0&&taskCount[j]>leftNum){
                    select = j;
                    leftNum = taskCount[j];
                }
            }
            if(select!=-1){
                //如果有任务可调度，他就是select
                taskCount[select]--;
                i++; //分配了一个任务
                totalTime += 1;
                for (int j = 0; j < 26; j++) {
                    if(freezeTime[j]!=0) freezeTime[j]--;
                }
                freezeTime[select] = n;
            }else {
                //无任务调度，直接快进到最小冷却时间结束的时刻
                //进入minFreeze==n+1的条件是freezeTime[j]>0||taskCount[j]==0 &&  freezeTime[j]==0||taskCount[j]==0
                //显然只能是taskCount[j]==0，即剩余全零了，那就可以直接退出了
                if(minFreeze==n+1) break;
                totalTime += minFreeze;
                for (int j = 0; j < 26; j++) {
                    if(freezeTime[j]!=0) freezeTime[j]-=minFreeze;
                }
            }
        }
        return totalTime;
    }
}
